package leetcode.pre50;

import java.util.*;

/**
 * 给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
 * <p>
 * 示例:
 * <p>
 * 输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
 * <p>
 * 输出:
 * [
 * ["ate","eat","tea"],
 * ["nat","tan"],
 * ["bat"]
 * ]
 * <p>
 * 说明：
 * <p>
 * 所有输入均为小写字母。
 * 不考虑答案输出的顺序。
 *
 * @since 2019/11/30 0030 下午 6:24
 */
public class Code49_字母异位词分组 {


    public static void main(String[] args) {
        String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
//        String []strs = {""};
//        List<List<String>> res = groupAnagrams(strs);
        List<List<String>> res = groupAnagrams1(strs);
        res.forEach(System.out::println);
    }

    /**
     * 方式1：遍历String数组，给每个位置按照字典排序，
     * <p>
     * 然后利用HashMap统计是否包含对应的key。Map的V存对应的答案List<String>.
     * <p>
     * 时间O(n*klogk)  k是strs中最大长度的那个
     */
    public static List<List<String>> groupAnagrams(String[] strs) {
        if (strs == null || strs.length == 0) {
            return new ArrayList<>();
        }
        Map<String, List<String>> map = new HashMap<>();
        for (int i = 0; i < strs.length; i++) {
            char[] chars = strs[i].toCharArray();
            Arrays.sort(chars);
            String key = String.valueOf(chars);
            //key是字典序，V是list
            if (!map.containsKey(key)) {
                map.put(key, new LinkedList<>());
            }
            //如果字典序已经被包含过了，则拿到对应的V，然后给V添加str[i]
            map.get(key).add(strs[i]);
        }
        //遍历map，添加到res。V的集合是Collection
        return new ArrayList<List<String>>(map.values());
    }

    /**
     * 方式2：遍历String数组，给每个位置字符串按计数分类，
     * <p>
     * 处理如下：统计这个字符串中字母的对应个数。并把所有个数排序设定为key。V同上。
     * <p>
     * 时间O(n*max(26,k))，空间O(n). k是strs中最长的那个
     */
    public static List<List<String>> groupAnagrams1(String[] strs) {
        if (strs == null || strs.length == 0) {
            return new ArrayList<>();
        }
        Map<String, List<String>> map = new HashMap<>();

        for (String str : strs) {
            //对str[i]进行统计。
            //26个字母
            int[] tables = new int[26];
            for (int i = 0; i < str.length(); i++) {
                tables[str.charAt(i) - 'a']++;
            }
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < tables.length; i++) {
                sb.append(tables[i]);
            }
            String sbKey = sb.toString();
            //key是字典序，V是list
            if (!map.containsKey(sbKey)) {
                map.put(sbKey, new LinkedList<>());
            }
            //如果字典序已经被包含过了，则拿到对应的V，然后给V添加str[i]
            map.get(sbKey).add(str);
        }
        //遍历map，添加到res。V的集合是Collection
        return new ArrayList<List<String>>(map.values());
    }

}
